package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202409;

import java.util.*;

public class leetcode20240918 {
    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity){
        Arrays.sort(buses);// 公交车到达时间排序
        Arrays.sort(passengers);// 乘客到达时间排序

        Deque<Integer> dq=new ArrayDeque<>();
        Set<Integer> set=new HashSet<>();

        for(int i=0;i<passengers.length;i++){
            dq.addLast(passengers[i]);
            set.add(passengers[i]);
        }

        int lastTime=0,lastCnt=0,lastCarIdx=0;
        for(int i=0;i<buses.length;i++){
            int cnt=0;
            while(!dq.isEmpty() && dq.peekFirst()<=buses[i] && cnt<capacity){
                cnt++;
                lastCnt=cnt;
                lastCarIdx=i;
                lastTime=dq.pollFirst();
            }
        }

        if(lastCarIdx<buses.length-1){
            return buses[buses.length-1];
        }

        if(lastCnt<capacity){
            lastTime=buses[buses.length-1];
        }

        while(set.contains(lastTime)){
            lastTime--;
        }

        return lastTime;

    }
}
